package dp.路径;

import java.util.Arrays;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 跳跃游戏ii45.java
 * @createTime 2024年02月29日 17:38:00
 */
public class 跳跃游戏ii45 {
	/*
  重复子问题：
  定义函数dp，表示到达位置i，最小的跳跃次数为dp[i]
  dp[i]的位置取决于,前面的能到这个位置的最小值，也就是如果num[j]+j>=i。那么dp[i]=min(dp[i], dp[j] + 1)
  baseCase:
  1. dp[0]=0;
  2. 所有的初始值为最大值（题目最大为1000）1001
   */
	public int jump(int[] nums) {
		int len = nums.length;
		int[] dp = new int[len];
		Arrays.fill(dp, 10001);
		dp[0] = 0;
		//从位置1开始
		for (int i = 1; i < len; i++) {
			//遍历到位置i所有的值，求最小值
			for (int j = 0; j < i; j++) {
				//
				if (j + nums[j] >= i) {
					dp[i] = Math.min(dp[i], dp[j] + 1);
				}
			}
		}
		return dp[len - 1];
	}
}
